#include <iostream>
#include <fstream>
#include <ctime>
#include "DSTree.h"

using namespace std;

const int MAXN = 0xfff00 + 10;
int array[MAXN];

int main()
{
/*
    ifstream in("../data/inputDate.in", ios::in);
    ofstream out("../data/ans.out", ios::out);

    ifstream in("../data/inputDate_all_insert.in", ios::in);
    ofstream out("../data/ans_all_insert.out", ios::out);

    ifstream in("../data/inputDate_all_find.in", ios::in);
    ofstream out("../data/ans_all_find.out", ios::out);

    ifstream in("../data/inputDate_all_update.in", ios::in);
    ofstream out("../data/ans_all_update.out", ios::out);
    */
    ifstream in("../data/inputDate_memory_test.in", ios::in);
    ofstream out("../data/ans_memory_test.out", ios::out);

    int t;
    in>>t;

    DSTree *dsTree = new DSTree();
    int test = 1;
    while (t--)
    {
        clock_t start = clock();
        out<<"case "<<test++<<":"<<endl;
        int n;
        in>>n;
        for (int i = 0; i < n; i++)
        {
            in>>array[i];
        }
        dsTree->buildTree(array, n);
        int m;
        in>>m;
        while (m--)
        {
            //dsTree->showTree();
            string str;
            in>>str;
            if (!str.compare("insert")){
                int index, value;
                in>>index>>value;
                dsTree->insert(index, value);
            }else if (!str.compare("update")){
                int index, value;
                in>>index>>value;
                dsTree->update(index, value);
            }else if (!str.compare("updateInterval")){
                int left, right, value;
                in>>left>>right>>value;
                dsTree->updateInterval(left, right, value);
            }else if (!str.compare("find")){
                int index;
                in>>index;
                int ans = dsTree->find(index);
                out<<ans<<endl;
            }else if (!str.compare("search")){
                int value;
                in>>value;
                int ans = dsTree->search(value);
                out<<ans<<endl;
            }else if (!str.compare("hide")){
                int left, right;
                in>>left>>right;
                dsTree->hide(left, right);
            }else if (!str.compare("remove")){
                int index;
                in>>index;
                dsTree->remove(index);
            }
        }
        dsTree->destroyTree();
        clock_t end = clock();

        clog << (double)(end - start) / CLOCKS_PER_SEC <<endl;
    }
    delete(dsTree);
    dsTree = NULL;
    out.close();
    in.close();
    return 0;
}
